package leecode;


/**
 * @Classname
 * @Description TODO
 * @Date 2021/7/19 22:08
 * @Created by Alberthch
 * 题目：旋转链表
 */
class Solution_61 {

    // 该链表只有构造方法，无法获取表头，也无法获取表尾
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode rotateRight(ListNode head, int k) {

        // 特殊情况
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        // 先拿到链表长度n,一定要从1开始，血的教训
        int n = 1;

        // 一定要是用新的变量来进行迭代，使得表头位置仍然可以用head来访问
        ListNode iter = head;
        while (iter.next != null) {
            n++;
            iter = iter.next;
        }

        if (k % n == 0) {
            return head;
        }

        // 得到实际移动次数，原链表后半部分
        int move = k % n;
        // 得到新链表表头,原链表前半部分
        int add = n - move;

        // 拿到新链表的前半部分start和后半部分head
        iter = head;
        ListNode start = null;
        // a-- 和 --a 的差别一定要搞清楚
        while (add-- > 0) {
            if (add == 0) {
                start = iter.next;
                // 从这里断开，则head就是新链表的后半部分
                iter.next = null;
            }

            iter = iter.next;

        }
        System.out.print("新链表前半部分：");
        printListNode(start);
        System.out.print("新链表后半部分：");
        printListNode(head);

        // 进行拼接
        ListNode res = start;
        while (move-- >0) {
            if (move == 0) {
                res.next = head;
            }
            res = res.next;
        }

        return start;
    }

    public static ListNode rotateRightLeecode(ListNode head, int k) {
        // 特殊情况的处理
        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        // 计算链表长度n，将head赋值给iter，使用iter去迭代操作，head指向表头，一定注意引用类型代表的是地址，类似指针
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        // 计算新链表的表头
        int add = n - k % n;

        // 特殊情况考虑
        if (add == n) {
            return head;
        }

        // 形成闭环
        iter.next = head;

        // 找到新链表的表头前一个位置
        while (add-- > 0) {
            iter = iter.next;
        }

        // 得到新链表表头，现在仍然是一个闭环
        ListNode res = iter.next;

        // 进行断开
        iter.next = null;
        return res;
    }


    public static void printListNode(ListNode head){
        while (head != null) {
            System.out.print(head.val);
            System.out.print(" ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        printListNode(head);
        // 引用类型作为实参，会改变实参的值,因此两个旋转链表函数只能够使用一个
        // printListNode(rotateRightLeecode(head,2));
        printListNode(rotateRight(head,2));
    }
}
